<head>
    <meta charset="UTF-8">
<title>历届试题 邮局</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>【问题描述】</div>
<div>C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。</div>
<div>&nbsp;</div>
<div>&nbsp; &nbsp; 现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。</div>
<div>&nbsp;</div>
<div>【输入格式】</div>
<div>&nbsp; &nbsp; 输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。</div>
<div>&nbsp; &nbsp; 接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。</div>
<div>&nbsp; &nbsp; 接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。</div>
<div>&nbsp; &nbsp; 在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。</div>
<div>&nbsp;</div>
<div>【输出格式】</div>
<div>&nbsp; &nbsp; 输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号）</div>
<div>&nbsp;</div>
<div>【样例输入】</div>
<div>5 4 2</div>
<div>0 0</div>
<div>2 0</div>
<div>3 1</div>
<div>3 3</div>
<div>1 1</div>
<div>0 1</div>
<div>1 0</div>
<div>2 1</div>
<div>3 2</div>
<div>&nbsp;</div>
<div>【样例输出】</div>
<div>2 4</div>
<div>&nbsp;</div>
<div>【数据规模和约定】</div>
<div>&nbsp; &nbsp; 对于30%的数据，1&lt;=n&lt;=10，1&lt;=m&lt;=10，1&lt;=k&lt;=5；</div>
<div>&nbsp; &nbsp; 对于60%的数据，1&lt;=m&lt;=20；</div>
<div>&nbsp; &nbsp; 对于100%的数据，1&lt;=n&lt;=50，1&lt;=m&lt;=25，1&lt;=k&lt;=10。</div>
<div>&nbsp;</div>